UVa/10827 - Maximum sum of a torus/10827.cpp

   1 #include <iostream>
   2 #include <vector>
   3
   4 using namespace std;
   5
   6 int main(){
   7   int runs;
   8   scanf("%d", &runs);
   9   while (runs--){
  10     int n;
  11     cin >> n;
  12     int m[n][n];
  13     for (int i=0; i<n; ++i){
  14       for (int j=0; j<n; ++j){
  15         scanf("%d", &m[i][j]);
  16       }
  17     }
  18
  19     int answer = 0;
  20     for (int i=0; i<n; ++i){
  21       vector<int> r(n, 0);
  22       int j = i;
  23       do{
  24         for (int k=0; k<n; ++k){
  25           r[k] += m[j][k];
  26         }
  27
  28         int sum = 0;
  29         for (int k=0; k<n; ++k){
  30           sum += r[k];
  31           if (sum > answer) answer = sum;
  32           if (sum < 0) sum = 0;
  33         }
  34
  35         sum = 0;
  36         int a = 0, b = 0;
  37         for (int k=0; k<n; ++k){
  38           sum += r[k];
  39           b += r[k];
  40           a = min(a, b);
  41           if (b > 0) b = 0;
  42         }
  43         if (sum - a > answer) answer = sum - a;
  44         j = (j+1)%n;
  45       }while(j != i);
  46     }
  47     printf("%d\n", answer);
  48   }
  49   return 0;
  50 }